#pragma once

namespace algorithm4cpp {

	/************************************************************************/
	/* 
	tag is the identifier of the record in dictionary. 
	It should be suitable for vector and set containers, i.e. copyable and comparable.
	*/
	/************************************************************************/
	template<typename TAG>
	class dictionary_tree : public enable_shared_from_this<dictionary_tree<TAG>>
	{
	private:
		typedef shared_ptr<dictionary_tree<TAG>>	tree_ptr;
		typedef hash_map<wchar_t, tree_ptr> tree_map;
		typedef vector<TAG>	tag_collection;
		typedef vector<tree_ptr>	path;
		typedef set<TAG>	tag_set;

	public:
		class tree_listener {
		public:
			virtual ~tree_listener() {}
			virtual void on_tree_appended( dictionary_tree * tree ) = 0;
			virtual void on_tree_removed( dictionary_tree * tree ) = 0;
		};

	public:
		dictionary_tree( wchar_t head )
			: head_(head)
			, tags_()
			, subtrees_()
			, listener_(NULL)
		{
		}

		virtual ~dictionary_tree(void) {
		}
	protected:
		dictionary_tree( const wchar_t * key, size_t length, TAG o, tree_listener * listener )
			: head_(*key)
			, tags_()
			, subtrees_()
			, listener_(listener)
		{
			merge( key + 1, length - 1, o );
		}

	public:
		wchar_t head() const 
		{
			return head_;
		}

		void merge( const wstring & key, TAG o )
		{
			merge( key.c_str(), key.length(), o );
		}

		void merge( const wchar_t * key, size_t length, TAG o )
		{
			if ( length == 0 ) {	// o on a leaf
				tags_.push_back(o);
				return ;
			}

			tree_ptr subtree = find_subtree( *key );
			if ( subtree ) {
				subtree->merge( key + 1, length - 1, o );
			} else {
				tree_ptr tree = create_tree(key, length, o);
				subtrees_[*key] = tree;
				if ( listener_ != NULL ) {
					listener_->on_tree_appended(tree.get());
				}
			}
		}

		void get_tags( tag_set & tags ) const
		{
			for ( size_t index = 0; index < tags_.size(); ++index ) {
				tags.insert(tags_[index]);
			}
		}

		//************************************
		// Method:    all_tags, include all subtrees tags
		// FullName:  everwanna::algorithm::dictionary_tree::all_tags
		// Access:    public 
		// Returns:   everwanna::algorithm::dictionary_tree::tag_collection
		// Qualifier: const
		//************************************
		void get_all_tags(tag_set & tags) const
		{
			get_tags( tags );

			for ( tree_map::const_iterator it = subtrees_.begin(); it != subtrees_.end(); ++it ) {
				it->second->get_all_tags( tags );
			}
		}

		void remove( const wstring & key, TAG o )
		{
			remove( key.c_str(), key.length(), o );
		}

		void remove( const wchar_t * key, size_t length, TAG o ) 
		{
			if ( length == 0 ) {
				return ;
			}

			path p;
			find_path( key, length, p );

			if ( p.size() != length ) {	// not found path
				return ;
			}

			p[p.size() - 1]->remove_tag(o);

			for ( size_t index = p.size() - 1; index > 0; --index ) {
				if ( p[index]->empty() ) {
					p[index-1]->remove_subtree( p[index]->head() );
				} else {
					break;
				}
			}

			if ( p[0]->empty() ) {
				remove_subtree( p[0]->head() );
			}
		}

		tree_listener * listener() const { return listener_; }
		void listener(tree_listener * val) { listener_ = val; }

		tree_ptr find_subtree( wchar_t sub_head ) const 
		{
			tree_map::const_iterator it = subtrees_.find(sub_head);
			if ( it == subtrees_.end() ) {
				return tree_ptr();
			}
			return it->second;
		}

		void find_path( const wchar_t * key, size_t length, path & p ) const
		{
			do_find_path(key, length, p);
			
			if ( p.size() != length ) {
				p.clear();
				return ;
			}

			for ( size_t index = 0; index < length; ++index ) {
				if ( p[index]->head() != key[index] ) {
					p.clear();
					return ;
				}
			}
		}

		bool has_subtree() const
		{
			return ! subtrees_.empty();
		}

	protected:
		void remove_subtree( wchar_t sub_head )
		{
			tree_map::const_iterator it = subtrees_.find( sub_head );
			if ( it != subtrees_.end() ) {
				tree_ptr tree = it->second;
				subtrees_.erase(it);
				if ( listener_ != NULL ) {
					listener_->on_tree_removed(tree.get());
				}
			}
		}

		void do_find_path( const wchar_t * key, size_t length, path &p ) const
		{
			if ( length == 0 ) {
				return ;
			}

			tree_ptr tree = find_subtree( *key );
			if ( tree ) {
				p.push_back(tree);
				tree->do_find_path( key + 1, length - 1, p );
			}
		}
		virtual tree_ptr create_tree( const wchar_t * key, size_t length, TAG o ) 
		{
			return tree_ptr( new dictionary_tree(key, length, o, listener_) );
		}

		bool empty() const 
		{
			return ( ! has_subtree() ) && ( ! has_tag() );
		}

		bool has_tag() const
		{
			return ! tags_.empty();
		}

		void remove_tag( TAG o )
		{
			for ( tag_collection::const_iterator it = tags_.begin(); it != tags_.end(); ++it ) {
				if ( *it == o ) {
					tags_.erase(it);
					return ;
				}
			}
		}

	private:
		wchar_t			head_;
		tag_collection	tags_;
		tree_map		subtrees_;
		tree_listener * listener_;
	};
}
